package 图论;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

//拓扑排序，深度优先
public class 课程表2 {
    //记录遍历过的节点，防止重复遍历同一个节点
    boolean[] visited;
    //记录一次traverse递归经过的节点
    boolean[] onPath;
    //记录图中是否有环
    boolean hasCycle = false;
    List<Integer> postorder = new ArrayList<>();
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        //因为图中不是所有节点都相连，所以要遍历每一个节点
        for (int i = 0; i < numCourses; i++) {
            traverse(graph,i);
        }
        if (hasCycle)
            return new int[]{};
        Collections.reverse(postorder);
        return postorder.stream().mapToInt(Integer::intValue).toArray();
    }
    //构建图
    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        //使用邻接表的方式来构建图
        List<Integer>[] graph = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            int from = prerequisite[1];
            int to = prerequisite[0];
            graph[from].add(to);
        }
        return graph;
    }
    //遍历图
    public void traverse(List<Integer>[] graph,int s){
        if (onPath[s])
            hasCycle = true;
        if (visited[s] || hasCycle)
            return;
        //将当前节点标记为已遍历
        visited[s] = true;
        onPath[s] = true;
        for (Integer integer : graph[s]) {
            traverse(graph,integer);
        }
        onPath[s] = false;
        postorder.add(s);
    }
}
